{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Swaps to Group All 1's Together II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSwaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最少交换次数来组合所有的 1 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>交换</strong> 定义为选中一个数组中的两个 <strong>互不相同</strong> 的位置并交换二者的值。</p>\n",
    "\n",
    "<p><strong>环形</strong> 数组是一个数组，可以认为 <strong>第一个</strong> 元素和 <strong>最后一个</strong> 元素 <strong>相邻</strong> 。</p>\n",
    "\n",
    "<p>给你一个 <strong>二进制环形</strong> 数组 <code>nums</code> ，返回在 <strong>任意位置</strong> 将数组中的所有 <code>1</code> 聚集在一起需要的最少交换次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [0,1,0,1,1,0,0]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>这里列出一些能够将所有 1 聚集在一起的方案：\n",
    "[0,<strong><em>0</em></strong>,<em><strong>1</strong></em>,1,1,0,0] 交换 1 次。\n",
    "[0,1,<em><strong>1</strong></em>,1,<em><strong>0</strong></em>,0,0] 交换 1 次。\n",
    "[1,1,0,0,0,0,1] 交换 2 次（利用数组的环形特性）。\n",
    "无法在交换 0 次的情况下将数组中的所有 1 聚集在一起。\n",
    "因此，需要的最少交换次数为 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [0,1,1,1,0,0,1,1,0]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>这里列出一些能够将所有 1 聚集在一起的方案：\n",
    "[1,1,1,0,0,0,0,1,1] 交换 2 次（利用数组的环形特性）。\n",
    "[1,1,1,1,1,0,0,0,0] 交换 2 次。\n",
    "无法在交换 0 次或 1 次的情况下将数组中的所有 1 聚集在一起。\n",
    "因此，需要的最少交换次数为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,1,0,0,1]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>得益于数组的环形特性，所有的 1 已经聚集在一起。\n",
    "因此，需要的最少交换次数为 0 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums[i]</code> 为 <code>0</code> 或者 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-swaps-to-group-all-1s-together-ii](https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-swaps-to-group-all-1s-together-ii](https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,0,1,1,0,0]', '[0,1,1,1,0,0,1,1,0]', '[1,1,0,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        # 好像并不麻烦啊\n",
    "        # 判断存在的时候基本就可以找到规律了\n",
    "        # 必须存在至少 n-1 个 0  n-2 个零 ...\n",
    "        # if same , then greed\n",
    "        # 看似冒泡 但是应该可以 faster\n",
    "        # 注意“失智\"\"行为 为什么， 以及什么情况下容易失去， 习惯?\n",
    "        ans  = 0\n",
    "        n   = len(grid)\n",
    "        rm  = [0]*n\n",
    "        fd = n-1\n",
    "\n",
    "        while fd:\n",
    "            start = n-fd\n",
    "            skip= 0\n",
    "\n",
    "            t = True\n",
    "            i = 0\n",
    "            while i < n :\n",
    "                t = True\n",
    "                if rm[i]:\n",
    "                    i+=1\n",
    "                    t = False\n",
    "                    continue\n",
    "                for j in range(start, n):\n",
    "                    if grid[i][j]==1:\n",
    "                        t = False\n",
    "                        break\n",
    "                i+=1\n",
    "                if t:\n",
    "                    break\n",
    "                else:\n",
    "                    skip +=1\n",
    "            if t:\n",
    "                ans += skip\n",
    "                rm[i-1]=1\n",
    "            else:\n",
    "                return -1\n",
    "            fd-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        length = len(grid)\n",
    "        pos = [0]*length\n",
    "        for i in range(length):\n",
    "            for j in range(length-1,-1,-1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        rs = 0\n",
    "        for i in range(length):\n",
    "            if pos[i]>i:\n",
    "                # 需要换\n",
    "                k = -1\n",
    "                for j in range(i+1, length):\n",
    "                    if pos[j] <= i:\n",
    "                        k = j\n",
    "                        break\n",
    "\n",
    "                if k == -1:\n",
    "                    return -1\n",
    "\n",
    "                rs += j-i\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j-1] = pos[j-1], pos[j]\n",
    "\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        def move(i, k):\n",
    "            tmp = pos[k]\n",
    "            for j in range(k, i, -1):\n",
    "                pos[j] = pos[j-1]\n",
    "            pos[i] = tmp\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if pos[j] <= i:\n",
    "                    k = j\n",
    "                    ans += k - i\n",
    "                    break\n",
    "            if k != -1:\n",
    "                move(i, k)\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judge(self, idx, line):\n",
    "        for i in range(idx, len(line)):\n",
    "            if line[i] == 1:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if self.judge(i + 1, grid[j]):\n",
    "                    grid.insert(i, grid.pop(j))\n",
    "                    count += (j - i)\n",
    "                    break\n",
    "                if j + 1 == n:\n",
    "                    return -1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        # 计算每一行最靠上可以存在的位置\n",
    "        row_min_idx = []\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    row_min_idx.append(j)\n",
    "                    break\n",
    "            else:\n",
    "                row_min_idx.append(0)\n",
    "\n",
    "        # print(row_min_idx)\n",
    "\n",
    "        # 贪心寻找、情景模拟\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # 如果当前行已符合要求\n",
    "            if row_min_idx[i] <= i:\n",
    "                continue\n",
    "\n",
    "            # 如果当前行不符合要求，寻找符合要求的行\n",
    "            for j in range(i + 1, n):\n",
    "                if row_min_idx[j] <= i:\n",
    "                    ans += j - i\n",
    "                    row_min_idx = row_min_idx[:i] + [row_min_idx[j]] + row_min_idx[i:j] + row_min_idx[j + 1:]\n",
    "                    break\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        zeros = []\n",
    "        for i in range(n):\n",
    "            zero = 0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if(grid[i][j] == 0):\n",
    "                    zero += 1\n",
    "                else:\n",
    "                    break\n",
    "            zeros.append(zero)\n",
    "\n",
    "        def getResult(i):\n",
    "            if(i == n):\n",
    "                return 0\n",
    "            if(zeros[i] < n-i-1):\n",
    "                for j in range(i+1,n):\n",
    "                    if(zeros[j] >= n-i-1):\n",
    "                        tmp = zeros[j]\n",
    "                        for k in range(j,i,-1):\n",
    "                            zeros[k] = zeros[k-1]\n",
    "                        zeros[i] = tmp\n",
    "                        return j-i+getResult(i+1)\n",
    "                return float('-inf')\n",
    "            else:\n",
    "                return getResult(i+1)\n",
    "        result = getResult(0)\n",
    "        return result if result > float('-inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "\n",
    "        def change(l):\n",
    "            ans = 0\n",
    "            for i in l[::-1]:\n",
    "                if i == 1:\n",
    "                    break\n",
    "                ans += 1\n",
    "            return ans \n",
    "        \n",
    "        grid = [change(i) for i in grid]\n",
    "        gg = sorted(grid)\n",
    "        for i in range(n):\n",
    "            if i > gg[i]:\n",
    "                return -1\n",
    "        \n",
    "        ans = 0\n",
    "        target = range(n-1,-1,-1)\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if grid[j] >= target[i]:\n",
    "                    #print(i,j)\n",
    "                    ans += j-i\n",
    "                    grid[i+1:j+1] = grid[i:j]\n",
    "                    break\n",
    "            #print(grid)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "\n",
    "        def move(i, j):\n",
    "            tmp = pos[j]\n",
    "            # 枚举到i的后一行，i+1\n",
    "            for k in range(j, i, -1):\n",
    "                pos[k] = pos[k-1]\n",
    "            pos[i] = tmp\n",
    "\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                # 找到了合适的位置\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    # 需要交换的行\n",
    "                    k = j\n",
    "                    break\n",
    "            # 处理交换过程\n",
    "            \n",
    "            if k != -1:\n",
    "                move(i, j)\n",
    "            \n",
    "            if k == -1:\n",
    "                return -1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        pos=[-1]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j]==1:\n",
    "                    pos[i]=j\n",
    "                    break\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            k=-1\n",
    "            for j in range(i,n):\n",
    "                if pos[j]<=i:\n",
    "                    ans+=j-i\n",
    "                    k=j\n",
    "                    break\n",
    "            if k==-1:\n",
    "                return -1\n",
    "            else:\n",
    "                for l in range(k,i,-1):\n",
    "                    pos[l],pos[l-1]=pos[l-1],pos[l]\n",
    "        \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if not grid:\n",
    "            return 0\n",
    "        count = [0] * n\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] != 0:\n",
    "                    break\n",
    "                cnt += 1\n",
    "            count[i] = cnt\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            t = n - i - 1\n",
    "            j = i\n",
    "            while j < n and count[j] < t:\n",
    "                j += 1\n",
    "            if j == n:\n",
    "                return -1\n",
    "            ans += j - i\n",
    "            while j > i:\n",
    "                count[j], count[j - 1] = count[j - 1], count[j]\n",
    "                j -= 1\n",
    "        return ans\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if not grid: return 0\n",
    "        zero_nums = []\n",
    "        for i in range(n):\n",
    "            j = n - 1\n",
    "            while j >= 0 and grid[i][j] == 0:\n",
    "                j -= 1\n",
    "            zero_nums.append(n - j - 1)\n",
    "        cnt = 0\n",
    "        for i in range(n - 1):\n",
    "            need_zeros = n - 1 - i\n",
    "            j = i\n",
    "            while j < len(zero_nums) and zero_nums[j] < need_zeros:\n",
    "                j += 1\n",
    "            if j == len(zero_nums):\n",
    "                return -1\n",
    "            cnt += j - i\n",
    "            while j > i:\n",
    "                zero_nums[j], zero_nums[j-1] = zero_nums[j-1], zero_nums[j]\n",
    "                j -= 1\n",
    "        return cnt \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        #----- 每行，最右侧1的位置(index)\n",
    "        most_right_1 = [-1 for _ in range(n)]\n",
    "        for r in range(n):\n",
    "            for c in range(n-1, -1, -1):\n",
    "                if grid[r][c] == 1:\n",
    "                    most_right_1[r] = c\n",
    "                    break\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "            find = False        #找到能交换的\n",
    "            find_r = -1         #能交换的行的行号（index）\n",
    "            #---- 从上往下搜，第一行可以交换的行\n",
    "            for rk in range(r, n):\n",
    "                if most_right_1[rk] <= r:\n",
    "                    find = True\n",
    "                    find_r = rk\n",
    "                    res += (rk - r)\n",
    "                    break \n",
    "            #---- 若没有合适的行\n",
    "            if find == False:\n",
    "                return -1\n",
    "            #---- 若有合适的行，交换\n",
    "            for rr in range(rk, r, -1):\n",
    "                most_right_1[rr], most_right_1[rr - 1] = most_right_1[rr - 1], most_right_1[rr]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        if not grid: return 0\n",
    "        # 统计每一行 从右向左连续0的个数\n",
    "        n = len(grid)\n",
    "        zero_nums = []\n",
    "        for i in range(n):\n",
    "            j = n - 1\n",
    "            while j >= 0 and grid[i][j] == 0: j -= 1\n",
    "            zero_nums.append(n - 1 - j)\n",
    "        # 贪心算法，从上到下查找满足条件的最小下标，即为交换到当前行的次数\n",
    "        cnt = 0\n",
    "        for i in range(n - 1):\n",
    "            need_zeros = n - 1 - i\n",
    "\n",
    "            j = i\n",
    "            while j < len(zero_nums) and zero_nums[j] < need_zeros: j += 1\n",
    "            \n",
    "            # 没找到则说明不满足条件\n",
    "            if j == len(zero_nums): return -1\n",
    "\n",
    "            # 增加交换次数\n",
    "            cnt += j - i\n",
    "            # 交换数值\n",
    "            while j > i:\n",
    "                zero_nums[j], zero_nums[j-1]= zero_nums[j-1], zero_nums[j]\n",
    "                j -= 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        if not grid: return 0\n",
    "        # 统计每一行 从右向左连续0的个数\n",
    "        n = len(grid)\n",
    "        zero_nums = []\n",
    "        for i in range(n):\n",
    "            j = n - 1\n",
    "            while j >= 0 and grid[i][j] == 0: j -= 1\n",
    "            zero_nums.append(n - 1 - j)\n",
    "        # 贪心算法，从上到下查找满足条件的最小下标，即为交换到当前行的次数\n",
    "        cnt = 0\n",
    "        for i in range(n - 1):\n",
    "            need_zeros = n - 1 - i\n",
    "\n",
    "            j = i\n",
    "            while j < len(zero_nums) and zero_nums[j] < need_zeros: j += 1\n",
    "            \n",
    "            # 没找到则说明不满足条件\n",
    "            if j == len(zero_nums): return -1\n",
    "\n",
    "            # 增加交换次数\n",
    "            cnt += j - i\n",
    "            # 交换数值\n",
    "            while j > i:\n",
    "                zero_nums[j], zero_nums[j-1]= zero_nums[j-1], zero_nums[j]\n",
    "                j -= 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "\n",
    "        # 计算每一行最靠上可以存在的位置\n",
    "        row_min_idx = []\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    row_min_idx.append(j)\n",
    "                    break\n",
    "            else:\n",
    "                row_min_idx.append(0)\n",
    "\n",
    "        # print(row_min_idx)\n",
    "\n",
    "        # 贪心寻找、情景模拟\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # 如果当前行已符合要求\n",
    "            if row_min_idx[i] <= i:\n",
    "                continue\n",
    "\n",
    "            # 如果当前行不符合要求，寻找符合要求的行\n",
    "            for j in range(i + 1, n):\n",
    "                if row_min_idx[j] <= i:\n",
    "                    ans += j - i\n",
    "                    row_min_idx = row_min_idx[:i] + [row_min_idx[j]] + row_min_idx[i:j] + row_min_idx[j + 1:]\n",
    "                    break\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        last1=[]\n",
    "        n = len(grid)\n",
    "        for row in grid:\n",
    "            pos = -1\n",
    "            for i in range(n-1,-1,-1):\n",
    "                if row[i]==1:\n",
    "                    pos=i\n",
    "                    break\n",
    "            last1.append(pos)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if last1[i]<=i:continue\n",
    "            found = False\n",
    "            for j in range(i+1,n):\n",
    "                if last1[j]<=i:\n",
    "                    found=True\n",
    "                    ans+=j-i\n",
    "                    for k in range(j,i,-1):\n",
    "                        last1[k],last1[k-1]=last1[k-1],last1[k]\n",
    "                    break\n",
    "            if not found: return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                # 找到了合适的位置\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    # 需要交换的行\n",
    "                    k = j\n",
    "                    break\n",
    "            # 处理交换过程\n",
    "            \n",
    "            if k != -1:\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j-1] = pos[j-1], pos[j]\n",
    "            \n",
    "            if k == -1:\n",
    "                return -1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "                n = len(grid)\n",
    "                f = [0 for i in range(n)]\n",
    "                for c in range(n-1,0,-1):\n",
    "                    for i,g in enumerate(grid):\n",
    "                        if g[n-c:] == [0] * c:\n",
    "                            f[i] = max(c,f[i])\n",
    "                c = n - 1;ans = 0\n",
    "                for i in range(n):\n",
    "                    if f[i] >= c:\n",
    "                        c -= 1\n",
    "                        continue\n",
    "                    flag = False\n",
    "                    for j in f[i+1:]:\n",
    "                        if j >= c:\n",
    "                            flag = True\n",
    "                            break\n",
    "                    if not flag:return -1\n",
    "                    for j in range(i+1,n):\n",
    "                        if f[j] >= c:\n",
    "                            ans += j - i\n",
    "                            for k in range(j,i,-1):\n",
    "                                f[k],f[k-1] = f[k-1],f[k]\n",
    "                            break\n",
    "                    \n",
    "                    c -= 1\n",
    "                    if c == 0:break\n",
    "                    \n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        # 记录下来每一行的1的最后的位置\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    k = j\n",
    "                    break\n",
    "            if  k != -1:\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j - 1] = pos[ j - 1], pos[j]\n",
    "            else:\n",
    "                return -1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        columns = len(grid[0])\n",
    "        zero_number_list = [0] * rows\n",
    "        swap_times = 0\n",
    "        for index in range(rows):\n",
    "            zero_number_list[index] = Check_Continuous_Zero_Number(grid, index)\n",
    "        target = columns - 1\n",
    "        for row in range(rows):\n",
    "            is_found = False\n",
    "            for target_row in range(row, rows):\n",
    "                if zero_number_list[target_row] >= target:\n",
    "                    swap_times += (target_row - row)\n",
    "                    is_found = True \n",
    "                    for swap_row in range(target_row, row, -1):\n",
    "                        zero_number_list[swap_row], zero_number_list[swap_row - 1]= zero_number_list[swap_row - 1], zero_number_list[swap_row] \n",
    "                    break \n",
    "            if is_found == False:\n",
    "                return -1\n",
    "            target -= 1\n",
    "        return swap_times\n",
    "\n",
    "def Check_Continuous_Zero_Number(grid, row):\n",
    "    zero_count = 0 \n",
    "    for cell in grid[row][::-1]:\n",
    "        if cell:\n",
    "            return zero_count \n",
    "        else:\n",
    "            zero_count += 1 \n",
    "    return zero_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "from collections import defaultdict\n",
    "from math import inf\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    k = j\n",
    "                    break\n",
    "\n",
    "            if k != -1:\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j - 1] = pos[j - 1], pos[j]\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        # j <= i\n",
    "        # 预处理\n",
    "        # 统计每一行最后一个1出现的位置\n",
    "        n = len(grid)\n",
    "        g = [-1]*n\n",
    "        for i in range(n):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j]:\n",
    "                    g[i] = j\n",
    "                    break\n",
    "        # 枚举每一行\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            # 枚举哪一行的0满足要求\n",
    "            k = -1\n",
    "            for j in range(i,n):\n",
    "                if g[j] <= i:\n",
    "                    ans += (j-i)\n",
    "                    k= j\n",
    "                    break\n",
    "            if k != -1:\n",
    "                for x in range(k,i,-1):\n",
    "                    g[x],g[x-1] = g[x-1],g[x]\n",
    "            else:\n",
    "                return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        l = [None] * n\n",
    "        for i in range(n):\n",
    "            k = 0\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] != 0:\n",
    "                    break\n",
    "                k += 1\n",
    "            l[i] = k\n",
    "        \n",
    "        a = 0\n",
    "        for i, v in enumerate(l):\n",
    "            need = n-i-1\n",
    "            if v >= need:\n",
    "                continue\n",
    "            for j in range(i+1, n):\n",
    "                l[i], l[j] = l[j], l[i]\n",
    "                a+=1\n",
    "                if l[i] >= need:\n",
    "                    break\n",
    "            if l[i] < need:\n",
    "                return -1\n",
    "            \n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "\n",
    "        pos = [-1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        def move(i, k):\n",
    "            for j in range(k, i, -1):\n",
    "                pos[j], pos[j-1] = pos[j-1], pos[j]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                # 找到了合适的j\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    k = j\n",
    "                    break\n",
    "            # 移动\n",
    "            if k != -1:\n",
    "                move(i, k)\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        zeros = []\n",
    "        for i in range(n):\n",
    "            zero = 0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if(grid[i][j] == 0):\n",
    "                    zero += 1\n",
    "                else:\n",
    "                    break\n",
    "            zeros.append(zero)\n",
    "\n",
    "        def getResult(i):\n",
    "            if(i == n):\n",
    "                return 0\n",
    "            if(zeros[i] < n-i-1):\n",
    "                for j in range(i+1,n):\n",
    "                    if(zeros[j] >= n-i-1):\n",
    "                        tmp = zeros[j]\n",
    "                        for k in range(j,i,-1):\n",
    "                            zeros[k] = zeros[k-1]\n",
    "                        zeros[i] = tmp\n",
    "                        return j-i+getResult(i+1)\n",
    "                return float('-inf')\n",
    "            else:\n",
    "                return getResult(i+1)\n",
    "        result = getResult(0)\n",
    "        return result if result > float('-inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        lst = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(n):\n",
    "            post = 0\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j]:\n",
    "                    break\n",
    "                post += 1\n",
    "            lst.append(post)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            zero = n-1-i\n",
    "            if lst[i] < zero:\n",
    "                for j in range(i+1, n):\n",
    "                    if lst[j] >= zero:\n",
    "                        for x in range(j, i, -1):\n",
    "                            lst[x], lst[x-1] = lst[x-1], lst[x]\n",
    "                            ans += 1\n",
    "                        break   \n",
    "                else:\n",
    "                    return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        # n*n的\n",
    "        # 第一步拿n-1的过去\n",
    "        # 第二步拿n-2的过去\n",
    "        # 直达拿1的过去\n",
    "        # 预处理\n",
    "        n = len(grid)\n",
    "        # 表示每一行最后一个1出现的位置\n",
    "        pos = [-1]*n\n",
    "        for i in range(n):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i,n):\n",
    "                if i >= pos[j]:\n",
    "                    ans += j-i\n",
    "                    k = j\n",
    "                    break\n",
    "            if k != -1:\n",
    "                # 将顺序调整\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j - 1] = pos[j - 1], pos[j]\n",
    "            else:\n",
    "                return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        gNew = []\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            if sum(grid[i]) == 0:\n",
    "                gNew.append(0)\n",
    "                continue\n",
    "            for j in range(n):\n",
    "                if grid[i][n - j - 1] == 1:\n",
    "                    gNew.append(n - j - 1)\n",
    "                    break\n",
    "        for i in range(n):\n",
    "            if gNew[i] <= i:\n",
    "                continue\n",
    "            for j in range(i + 1, n):\n",
    "                if gNew[j] <= i:\n",
    "                    count += j - i\n",
    "                    for k in range(j, i, -1):\n",
    "                        gNew[k] = gNew[k - 1]\n",
    "                    flag = 0\n",
    "                    break\n",
    "                flag = -1\n",
    "            if flag == -1:\n",
    "                return -1 \n",
    "        \n",
    "        return count\n",
    "\n",
    "\n",
    "        print(gNew)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        def move(i, k):\n",
    "            tmp = pos[k]\n",
    "            for j in range(k, i, -1):\n",
    "                pos[j] = pos[j-1]\n",
    "            pos[i] = tmp\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if pos[j] <= i:\n",
    "                    k = j\n",
    "                    ans += k - i\n",
    "                    break\n",
    "            if k != -1:\n",
    "                move(i, k)\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        columns = len(grid[0])\n",
    "        zero_number_list = [0] * rows\n",
    "        swap_times = 0\n",
    "        for index in range(rows):\n",
    "            zero_number_list[index] = Check_Continuous_Zero_Number(grid, index)\n",
    "        target = columns - 1\n",
    "        for row in range(rows):\n",
    "            is_found = False\n",
    "            for target_row in range(row, rows):\n",
    "                if zero_number_list[target_row] >= target:\n",
    "                    swap_times += (target_row - row)\n",
    "                    is_found = True \n",
    "                    for swap_row in range(target_row, row, -1):\n",
    "                        zero_number_list[swap_row], zero_number_list[swap_row - 1]= zero_number_list[swap_row - 1], zero_number_list[swap_row] \n",
    "                    break \n",
    "            if is_found == False:\n",
    "                return -1\n",
    "            target -= 1\n",
    "        return swap_times\n",
    "\n",
    "def Check_Continuous_Zero_Number(grid, row):\n",
    "    zero_count = 0 \n",
    "    for cell in grid[row][::-1]:\n",
    "        if cell:\n",
    "            return zero_count \n",
    "        else:\n",
    "            zero_count += 1 \n",
    "    return zero_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = [0] * n\n",
    "        # m表示每行的后缀0个数\n",
    "        for i in range(n):\n",
    "            m[i] = n\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if grid[i][j] == 1:\n",
    "                    m[i] = n - j - 1\n",
    "                    break\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            t = 0\n",
    "            for k in range(n):\n",
    "                if m[k] == -1: continue\n",
    "                if m[k] >= n - i - 1:\n",
    "                    res += t\n",
    "                    m[k] = -1\n",
    "                    break\n",
    "                t += 1\n",
    "            else:\n",
    "                return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        zeros = []\n",
    "        for i in range(n):\n",
    "            zero = 0\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if(grid[i][j] == 0):\n",
    "                    zero += 1\n",
    "                else:\n",
    "                    break\n",
    "            zeros.append(zero)\n",
    "\n",
    "        def getResult(i):\n",
    "            if(i == n):\n",
    "                return 0\n",
    "            if(zeros[i] < n-i-1):\n",
    "                for j in range(i+1,n):\n",
    "                    if(zeros[j] >= n-i-1):\n",
    "                        tmp = zeros[j]\n",
    "                        for k in range(j,i,-1):\n",
    "                            zeros[k] = zeros[k-1]\n",
    "                        zeros[i] = tmp\n",
    "                        return j-i+getResult(i+1)\n",
    "                return float('-inf')\n",
    "            else:\n",
    "                return getResult(i+1)\n",
    "        result = getResult(0)\n",
    "        return result if result > float('-inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        pos = [-1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if grid[i][j] == 1:\n",
    "                    pos[i] = j\n",
    "                    break\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if pos[j] <= i:\n",
    "                    ans += j - i\n",
    "                    k = j\n",
    "                    break\n",
    "            \n",
    "            if k != -1:\n",
    "                for j in range(k, i, -1):\n",
    "                    pos[j], pos[j - 1] = pos[j - 1], pos[j]\n",
    "            else:\n",
    "                return -1\n",
    "    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        \n",
    "        n = len(grid)\n",
    "        \n",
    "        ans = 0\n",
    "        left = [[0] * (n + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if j == n - 1:\n",
    "                    left[i][j] = int(grid[i][j] == 0)\n",
    "                elif grid[i][j] == 0:\n",
    "                    left[i][j] = left[i][j + 1] + 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            need = n - i - 1\n",
    "            if left[i][i + 1] == need:\n",
    "                continue\n",
    "            j = i + 1\n",
    "            while j < n and left[j][i + 1] < need:\n",
    "                j += 1\n",
    "            if j == n:\n",
    "                return -1\n",
    "            # print(i, j)\n",
    "            ans += j - i\n",
    "            for k in range(j, i, -1):\n",
    "                left[k], left[k - 1] = left[k - 1], left[k]\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        gNew = []\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            if sum(grid[i]) == 0:\n",
    "                gNew.append(0)\n",
    "                continue\n",
    "            for j in range(n):\n",
    "                if grid[i][n - j - 1] == 1:\n",
    "                    gNew.append(n - j - 1)\n",
    "                    break\n",
    "        for i in range(n):\n",
    "            print(gNew)\n",
    "            if gNew[i] <= i:\n",
    "                continue\n",
    "            for j in range(i + 1, n):\n",
    "                if gNew[j] <= i:\n",
    "                    count += j - i\n",
    "                    for k in range(j, i, -1):\n",
    "                        gNew[k] = gNew[k - 1]\n",
    "                    flag = 0\n",
    "                    break\n",
    "                flag = -1\n",
    "            if flag == -1:\n",
    "                return -1 \n",
    "        \n",
    "        return count\n",
    "\n",
    "\n",
    "        print(gNew)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = [0] * n\n",
    "        # m表示每行的后缀0个数\n",
    "        for i in range(n):\n",
    "            m[i] = n\n",
    "            for j in reversed(range(n)):\n",
    "                if grid[i][j] == 1:\n",
    "                    m[i] = n - j - 1\n",
    "                    break\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            t = 0\n",
    "            for k in range(n):\n",
    "                if m[k] == -1: continue\n",
    "                if m[k] >= n - i - 1:\n",
    "                    res += t\n",
    "                    m[k] = -1\n",
    "                    break\n",
    "                t += 1\n",
    "            else:\n",
    "                return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        tail = [0] * n\n",
    "        for i in range(n): # 求每一行末尾连续 0 个数\n",
    "            cnt = 0\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if grid[i][j] != 0:\n",
    "                    tail[i] = j\n",
    "                    break\n",
    "                cnt += 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            for j in range(i, n):\n",
    "                if tail[j] <= i:\n",
    "                    ans += j - i\n",
    "                    k = j\n",
    "                    break\n",
    "            if -1 == k:\n",
    "                return -1\n",
    "            else:\n",
    "                for j in range(k, i, - 1):\n",
    "                    tail[j], tail[j-1] = tail[j-1],tail[j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        n_0 = []\n",
    "        for r in grid:\n",
    "            temp = 0\n",
    "            for i in range(n-1, -1, -1):\n",
    "                if r[i] == 0:\n",
    "                    temp += 1\n",
    "                else:\n",
    "                    break\n",
    "            n_0.append(temp)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(len(n_0)):\n",
    "                if n_0[j] >= n-1-i:\n",
    "                    ans += j\n",
    "                    n_0 = n_0[:j] + n_0[j+1:]\n",
    "                    break\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        sum_ = sum(nums)\n",
    "        n = len(nums)\n",
    "        if sum_ == n or sum_ == 0:\n",
    "            return 0\n",
    "\n",
    "        window_sum = 0\n",
    "        for i in range(sum_):\n",
    "            window_sum += nums[i]\n",
    "\n",
    "        res = sum_ - window_sum\n",
    "        for i in range(n-1):\n",
    "            window_sum += nums[(i+sum_) % n] - nums[i]\n",
    "            res = min(res, sum_ - window_sum)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        cnt=sum(nums)\n",
    "        if cnt==n or cnt==0 or cnt==1:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        temp =0\n",
    "        for i in range(0,cnt):\n",
    "            if nums[i]==0:\n",
    "                temp+=1\n",
    "        ans=temp\n",
    "        for i in range(0,cnt+n):\n",
    "            if nums[(i+cnt)%n]==0:\n",
    "                temp+=1\n",
    "            if nums[i%n]==0:\n",
    "                temp-=1\n",
    "            ans =min(ans,temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        oneCnt = nums.count(1)\n",
    "        preAns = nums[1 : n - oneCnt + 1].count(1)\n",
    "        ans = preAns\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == 1:\n",
    "                preAns -= 1\n",
    "            if nums[i - oneCnt] == 1:\n",
    "                preAns += 1\n",
    "            ans = min(ans, preAns)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        one = self.get_length(nums, target=1)\n",
    "        zero = self.get_length(nums, target=0)\n",
    "        \n",
    "        return min(one, zero)\n",
    "    \n",
    "    def get_length(self, nums, target):\n",
    "        left = 0\n",
    "        window = defaultdict(lambda: 0)\n",
    "        count = Counter(nums)\n",
    "        cnt = len(nums)\n",
    "\n",
    "        for right, c in enumerate(nums):\n",
    "            window[c] += 1\n",
    "            \n",
    "            if right >= count[target]:\n",
    "                d = nums[left]\n",
    "                window[d] -= 1\n",
    "                left += 1\n",
    "\n",
    "            if right - left + 1 == count[target]:\n",
    "                cnt = min(cnt, count[target] - window[target])\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums) -> int:\n",
    "        cnt = 0 # 1 的个数\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                cnt += 1\n",
    "\n",
    "        # 使用长度为 cnt 的滑动窗口，查看该窗口中有多少个数不是 1， 找出最小的窗口。\n",
    "        # 因为是环形的，所以采用破环成链的常规套路。\n",
    "        new_nums = [0] * (2 * len(nums))\n",
    "        for i in range(len(nums)):\n",
    "            new_nums[i] = new_nums[i + len(nums)] = nums[i]\n",
    "\n",
    "        window_cnt, ans = 0, cnt\n",
    "        for i, x in enumerate(new_nums):\n",
    "            if x:\n",
    "                window_cnt += 1\n",
    "\n",
    "            if i >= cnt:\n",
    "                if new_nums[i - cnt]:\n",
    "                    window_cnt -= 1\n",
    "\n",
    "            ans = min(ans, cnt - window_cnt)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        k = nums.count(1)\n",
    "\n",
    "        if k < 2:\n",
    "            return 0\n",
    "\n",
    "        arr = nums + nums\n",
    "        l *= 2\n",
    "\n",
    "        current = arr[0:k].count(1)\n",
    "        res = current\n",
    "        for i in range(1, l - k + 1):\n",
    "            current = current - arr[i-1] + arr[i+k-1]\n",
    "            res = max(res, current)\n",
    "\n",
    "        return k - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        s = sum(nums) # 1 的个数\n",
    "        if s==0:\n",
    "            return 0\n",
    "        nums = nums*2 # 拼接原数组\n",
    "        window = sum(nums[:s-1]) # 滑窗的和\n",
    "        ans = len(nums)\n",
    "        for r in range(s-1, len(nums)):\n",
    "            window += nums[r] # 右端点加入\n",
    "            ans = min(ans, s-window) # 还差几个 1 就要挪动几次\n",
    "            window -= nums[r-s+1] # 左端点出去\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        cnt = c[1]\n",
    "        arr = nums + nums\n",
    "        n = len(arr)\n",
    "        c = Counter(nums[:cnt])\n",
    "        l = 0\n",
    "        ans = cnt - c[1]\n",
    "        for i in range(cnt, n):\n",
    "            c[arr[i - cnt]] -= 1\n",
    "            c[arr[i]] += 1\n",
    "            ans = min(ans, cnt - c[1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt_ones = sum(nums)\n",
    "        new_nums = nums + nums\n",
    "        sums = 0\n",
    "        ans = n\n",
    "        for i in range(cnt_ones):\n",
    "            sums += new_nums[i]\n",
    "            ans = min(ans, cnt_ones - sums)\n",
    "        for i in range(1, 2 * n - cnt_ones):\n",
    "            sums -= new_nums[i - 1]\n",
    "            sums += new_nums[i + cnt_ones - 1]\n",
    "            ans = min(ans, cnt_ones - sums)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        count=nums.count(1)\n",
    "        if count==0:\n",
    "            return 0\n",
    "        key=nums[:count]\n",
    "        nums=nums+key[:]\n",
    "        key=deque(key)\n",
    "        res=key.count(0)\n",
    "        ans=res\n",
    "        for i in range(count,len(nums)):\n",
    "            key.append(nums[i])\n",
    "            if nums[i]==0:\n",
    "                res+=1               \n",
    "            if key.popleft()==0:\n",
    "                res-=1\n",
    "            ans=min(ans,res)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = nums.count(1)\n",
    "        qzh = list()\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 1:\n",
    "                cnt += 1\n",
    "            qzh.append(cnt)\n",
    "        # print(qzh)\n",
    "        res = m - qzh[m - 1]\n",
    "        for i in range(1, n):\n",
    "            if i + m - 1 < n:\n",
    "                cnt = m - qzh[i + m - 1] + qzh[i - 1]\n",
    "            else:\n",
    "                cnt = m - qzh[i + m - n - 1] - qzh[-1] + qzh[i - 1]\n",
    "            # print(i, cnt)\n",
    "            res = min(res, cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        prefix = list(accumulate([0] + nums))\n",
    "        one = sum(nums)\n",
    "        n = len(nums)\n",
    "        \n",
    "        ans = one\n",
    "        # 检查尾部为 [k, n] 的区间\n",
    "        for i in range(one, n + 1):\n",
    "            val = prefix[i] - prefix[i - one]\n",
    "            ans = min(ans, one - val)\n",
    "        # 检查首尾相接的两段区间 [0, i] + [n - k + i, n]\n",
    "        for i in range(1, one):\n",
    "            val = prefix[i] + (prefix[n] - prefix[n - (one - i)])\n",
    "            ans = min(ans, one - val)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        k = sum(nums)\n",
    "        nums2 = nums\n",
    "        nums2.extend(nums2)\n",
    "        ones = sum(nums2[:k])\n",
    "        res = k - ones\n",
    "        for i in range(1, n):\n",
    "            if nums2[i+k-1] == 1:\n",
    "                ones += 1\n",
    "            if nums2[i-1] == 1:\n",
    "                ones -= 1\n",
    "            res = min(res, k - ones)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        k=sum(nums)\n",
    "        nums=nums*2\n",
    "        ans=temp=sum(nums[:k])\n",
    "        for i in range(n):\n",
    "            if nums[i]!=nums[i+k]:\n",
    "                temp+=nums[i+k]-nums[i]\n",
    "                ans=max(ans,temp)\n",
    "        return k-ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      one = cnt = 0\n",
    "      for j in nums:\n",
    "        if j == 1:\n",
    "          one += 1\n",
    "      nums += nums\n",
    "      for i in range(one):\n",
    "        j = nums[i]\n",
    "        cnt += j == 1\n",
    "      ans = one-cnt\n",
    "      for i in range(one,n+one):\n",
    "        j = nums[i]\n",
    "        cnt += (j == 1)- (nums[i-one] == 1)\n",
    "        ans = min(ans,one-cnt)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      one = cnt = 0\n",
    "      ans = inf\n",
    "      for j in nums:\n",
    "        if j == 1:\n",
    "          one += 1\n",
    "      nums += nums\n",
    "      for i in range(one):\n",
    "        j = nums[i]\n",
    "        cnt += j==1\n",
    "      ans = one-cnt\n",
    "      for i in range(one,n+one):\n",
    "        j = nums[i]\n",
    "        cnt += (j == 1)- (nums[i-one] == 1)\n",
    "        ans = min(ans,one-cnt)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        \n",
    "        # 定长滑动窗口\n",
    "        # 这k个1都需要移在一起\n",
    "        k = sum(nums)\n",
    "        nums = nums+nums\n",
    "        left = 0\n",
    "        # 统计其中的1\n",
    "        count = 0\n",
    "        res = 0\n",
    "        for right in range(len(nums)):\n",
    "            if nums[right] == 1:\n",
    "                count += 1\n",
    "            while right - left + 1 > k:\n",
    "                if nums[left] == 1:\n",
    "                    count -= 1\n",
    "                left += 1\n",
    "            res = max(res,count)\n",
    "        return k - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        total_ones = sum(nums)\n",
    "        if total_ones <= 1:\n",
    "            return 0\n",
    "\n",
    "        max_ones = 0\n",
    "        current_ones = 0\n",
    "        window_size = total_ones\n",
    "\n",
    "        # Extend the array to simulate the circular nature\n",
    "        nums = nums * 2\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if i >= window_size:\n",
    "                current_ones -= nums[i - window_size]\n",
    "            current_ones += nums[i]\n",
    "            max_ones = max(max_ones, current_ones)\n",
    "\n",
    "        return total_ones - max_ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        one = nums.count(1)\n",
    "        n = len(nums)\n",
    "        nums = nums + nums\n",
    "        l = r = 0\n",
    "        cnt = 0\n",
    "        ans = inf\n",
    "        while r < len(nums):\n",
    "            if nums[r] == 1:\n",
    "                cnt += 1\n",
    "            while r - l + 1 > one:\n",
    "                if nums[l] == 1:\n",
    "                    cnt -= 1\n",
    "                l += 1\n",
    "            if r - l + 1 == one:\n",
    "                ans = min(ans, one - cnt)\n",
    "            r += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        window_size=sum(nums)\n",
    "        dp=[0 for _ in range(len(nums))]\n",
    "        if window_size==0 or not nums or window_size==len(nums):\n",
    "            return 0\n",
    "        for i in range(window_size):\n",
    "            dp[0]+=nums[i]\n",
    "        dpmax=dp[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i]=dp[i-1]-nums[i-1]+nums[(i+window_size-1)%len(nums)]\n",
    "            dpmax=max(dp[i],dpmax)\n",
    "        return window_size-dpmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        c = Counter(nums)[1]\n",
    "        nums = nums * 2\n",
    "\n",
    "        left = 0\n",
    "        right = left + c - 1\n",
    "        cnt = Counter(nums[left:right])[1]\n",
    "        ans = math.inf\n",
    "        while right < n + c:\n",
    "            if nums[right] == 1:\n",
    "                cnt += 1\n",
    "            ans = min(ans, c - cnt)\n",
    "            if nums[left] == 1:\n",
    "                cnt -= 1\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        c1=nums.count(1)\n",
    "        nums=nums*2\n",
    "        que=deque()\n",
    "        res=ans=0\n",
    "        for i in range(2*n):\n",
    "            q=nums[i]\n",
    "            ans+=q\n",
    "            que.append(q)\n",
    "            if len(que)>c1:\n",
    "                ans-=que.popleft()\n",
    "            if len(que)==c1:\n",
    "                res=max(res,ans)\n",
    "        return c1-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums):\n",
    "        # 环形数组：将原数组复制一份拷贝到数组末尾，即可破环成链\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        v = []\n",
    "\n",
    "        for i in range(n * 2):\n",
    "            if i < n:\n",
    "                if nums[i]:\n",
    "                    cnt += 1  # 统计1的个数\n",
    "            v.append(nums[i % n])\n",
    "\n",
    "        res = n\n",
    "        l = 0\n",
    "        num = 0\n",
    "\n",
    "        for r in range(2 * n):\n",
    "            num += v[r]\n",
    "\n",
    "            while r - l + 1 > cnt:\n",
    "                num -= v[l]\n",
    "                l += 1\n",
    "\n",
    "            res = min(res, cnt - num)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums):\n",
    "        # 环形数组：将原数组复制一份拷贝到数组末尾，即可破环成链\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        v = []\n",
    "\n",
    "        for i in range(n * 2):\n",
    "            if i < n:\n",
    "                if nums[i]:\n",
    "                    cnt += 1  # 统计1的个数\n",
    "            v.append(nums[i % n])\n",
    "\n",
    "        res = n\n",
    "        l = 0\n",
    "        num = 0\n",
    "\n",
    "        for r in range(2 * n):\n",
    "            num += v[r]\n",
    "\n",
    "            while r - l + 1 > cnt:\n",
    "                num -= v[l]\n",
    "                l += 1\n",
    "\n",
    "            res = min(res, cnt - num)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        k = nums.count(1)\n",
    "        nums = 2 * nums\n",
    "        mx = cnt = nums[:k].count(1)\n",
    "        for a, b in zip(nums[k:], nums):\n",
    "            cnt += int(a == 1)\n",
    "            cnt -= int(b == 1)\n",
    "            if cnt > mx:\n",
    "                mx = cnt\n",
    "        return k - mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        k = nums.count(1)\n",
    "        ans, c = inf, 0\n",
    "        dq = deque()\n",
    "        for x in nums * 2:\n",
    "            dq.append(x)\n",
    "            c += x\n",
    "            if len(dq) > k: c -= dq.popleft()\n",
    "            if len(dq) == k: ans = min(ans, k-c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        ##滑动窗口\n",
    "        n=len(nums)\n",
    "        total=sum(nums)\n",
    "        ans=inf\n",
    "        presum=list(accumulate(nums))\n",
    "        for right in range(total,n):\n",
    "            t=presum[right]-presum[right-total]\n",
    "            ans=min(ans,total-t)\n",
    "        for right in range(0,total):\n",
    "            t=presum[right]+presum[n-1]-presum[n-(total-right)]\n",
    "            ans=min(ans,total-t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        s = sum(nums)\n",
    "        if s == 0: return 0\n",
    "        f = [0] * len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0: f[i] = nums[i] ^ 1\n",
    "            if 0 < i < s: f[i] = f[i-1] + (nums[i] ^ 1)\n",
    "            if i >= s: f[i] = f[i-1] + nums[i-s] - nums[i]\n",
    "        res1 = min(f[s-1:])\n",
    "        \n",
    "        f_ = [0] * len(nums)\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if i == len(nums)-1: f_[i] = (nums[i] ^ 1)\n",
    "            if len(nums)-1 > i >= len(nums) - s : f_[i] = f_[i+1] + (nums[i] ^ 1)\n",
    "        res2 = res1\n",
    "        for i in range(s-1):\n",
    "            res2 = min(res2 , f[i] + f_[len(nums) - s + i + 1])\n",
    "        return min(res1,res2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        leng = len(nums)\n",
    "        res = [nums[0]] * leng\n",
    "        for i in range(1,leng):\n",
    "            res[i] = res[i-1] + nums[i]\n",
    "        one = nums.count(1)\n",
    "        min_value = one\n",
    "        for i in range(leng):\n",
    "            if i < one:\n",
    "                ans = res[i] + res[leng-1]-res[leng-one+i]\n",
    "            else:\n",
    "                ans = res[i]-res[i-one]\n",
    "            if one-ans < min_value:\n",
    "                min_value = one-ans\n",
    "\n",
    "        return min_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        leng = len(nums)\n",
    "        res = [nums[0]] * leng\n",
    "        for i in range(1,leng):\n",
    "            res[i] = res[i-1] + nums[i]\n",
    "        one = nums.count(1)\n",
    "        min_value = one\n",
    "        for i in range(leng):\n",
    "            if i < one:\n",
    "                ans = res[i] + res[leng-1]-res[leng-one+i]\n",
    "            else:\n",
    "                ans = res[i]-res[i-one]\n",
    "            if one-ans < min_value:\n",
    "                min_value = one-ans\n",
    "\n",
    "        return min_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        count = sum(nums)\n",
    "        \n",
    "        if count == 0 or count == len(nums):\n",
    "            return 0\n",
    "        \n",
    "        result = float('inf')\n",
    "        for i in range(count - 1):\n",
    "            nums.append(nums[i])\n",
    "        \n",
    "        dp = [0] * (len(nums) - count + 1)\n",
    "        dp[0] = count\n",
    "        for i in range(count):\n",
    "            dp[0] -= nums[i]\n",
    "\n",
    "        for i in range(1, len(nums) - count + 1):\n",
    "            if nums[i - 1] == nums[i + count - 1]:\n",
    "                dp[i] = dp[i - 1]\n",
    "            elif nums[i - 1] == 1:\n",
    "                dp[i] = dp[i - 1] + 1\n",
    "            elif nums[i - 1] == 0:\n",
    "                dp[i] = dp[i - 1] - 1\n",
    "        print(dp)\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        size=len(nums)\n",
    "        presum=[]\n",
    "        d=Counter(nums)\n",
    "        for i in nums:\n",
    "            presum.append(i+(presum[-1] if len(presum)>0 else 0))\n",
    "        ans=d[1]\n",
    "        for l in range(size): #取区间\n",
    "            r=l+d[1]\n",
    "            if r<=size:\n",
    "                c0=r-l-(presum[r-1]-(presum[l-1] if l-1>=0 else 0))\n",
    "            else:\n",
    "                c0=r-l-(presum[(r-1)%size]+(presum[size-1]-presum[l-1]))             \n",
    "            ans=min(ans,c0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        # dp[i] 以 i 为起点的固定窗口长度（1的总数）下1的个数\n",
    "        ones = sum(nums)\n",
    "        dp = [0 for _ in range(len(nums))]\n",
    "        if ones == len(nums) or ones == 0: return 0\n",
    "        # 计算dp[0]\n",
    "        for i in range(ones):\n",
    "            dp[0] += nums[i]\n",
    "        ans = dp[0]\n",
    "        # 计算dp[i]\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = dp[i - 1] - nums[i - 1] + nums[(i + ones - 1) % len(nums)]\n",
    "            ans = max(dp[i], ans)\n",
    "        return ones - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        val = nums.count(1)\n",
    "        res = [0]\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n*2):\n",
    "            if nums[i%n]==1:\n",
    "                res.append(res[-1]+1)\n",
    "            else:\n",
    "                res.append(res[-1])\n",
    "            if i>=val:\n",
    "                ans = max(ans, res[i]-res[i-val])\n",
    "        return val-ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n=len(nums)\n",
    "        if nums==[1]*n:\n",
    "                return  0\n",
    "        \n",
    "        def midswap(nums):\n",
    "                       \n",
    "            nums1 = 0\n",
    "                      \n",
    "            n = len(nums)\n",
    "            \n",
    "            for num in nums:\n",
    "                if num == 1:\n",
    "                    nums1 += 1\n",
    "                    \n",
    "            pre=[0]\n",
    "            total=0\n",
    "            for i in range(n+nums1):\n",
    "                total+=nums[i%n]\n",
    "                pre.append(total)        \n",
    "                    \n",
    "            \n",
    "            ans=n\n",
    "            for l in range(n):\n",
    "                ans=min(ans,nums1-(pre[l+nums1]-pre[l]))\n",
    "        \n",
    "            return ans\n",
    "            \n",
    "        return midswap(nums)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        leng = len(nums)\n",
    "        res = [0] * (leng+1)\n",
    "        for i in range(leng):\n",
    "            res[i+1] = res[i] + nums[i]\n",
    "        res = res[1:]\n",
    "        one = nums.count(1)\n",
    "        ans = sum(nums[:one])\n",
    "        min_value = one-ans\n",
    "        for i in range(leng):\n",
    "            # ans += nums[i]-nums[i-one]\n",
    "            if i < one:\n",
    "                ans = res[i] + res[leng-1]-res[leng-one+i]\n",
    "            else:\n",
    "                ans = res[i]-res[i-one]\n",
    "            if one-ans < min_value:\n",
    "                min_value = one-ans\n",
    "\n",
    "        return min_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        presums=[0]\n",
    "        for i in nums: presums.append(presums[-1]+i)     \n",
    "        #print(presums)\n",
    "        k=sum(nums) \n",
    "        for i in range(k): \n",
    "            presums.append(presums[-1]+nums[i]) \n",
    "        #print(presums)\n",
    "        n=len(nums)\n",
    "        ret=len(nums) \n",
    "        for i in range(1,n+1): \n",
    "            #print(i-1,presums[i+k]-presums[i-1])\n",
    "            ret=min(ret,k-(presums[i+k-1]-presums[i-1])) \n",
    "        return ret \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        pre = [0 for i in range(n + 5)]\n",
    "        aft = [0 for i in range(n + 5)]\n",
    "        for i in range(n):\n",
    "            pre[i] = pre[i - 1] + (a[i] == 0)\n",
    "        for i in range(n - 1,-1,-1):\n",
    "            aft[i] = aft[i + 1] + (a[i] == 0)\n",
    "        cnt = a.count(1)\n",
    "        ans = 10000000\n",
    "        for i in range(cnt):\n",
    "            j = n - 1 - (cnt - i - 1) + 1\n",
    "            ans = min(ans , pre[i] + aft[j])\n",
    "            #if pre[i] + aft[j] == 1: print(i,j)\n",
    "        for i in range(cnt , n):\n",
    "            ans = min(ans , pre[i] - pre[i - cnt])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "\n",
    "      count_1 = 0\n",
    "      front_1_sum = [0] * (len(nums) + 1)\n",
    "      for i, num in enumerate(nums):\n",
    "        if num == 1:\n",
    "          count_1 += 1\n",
    "        front_1_sum[i] = count_1\n",
    "\n",
    "      print(front_1_sum)\n",
    "\n",
    "      start = 0\n",
    "      end = count_1 - 1\n",
    "      max_1_num = 0\n",
    "      while start < len(nums):\n",
    "        \n",
    "        if start <= end and (tmp := front_1_sum[end] - front_1_sum[start-1]) > max_1_num:\n",
    "          max_1_num = tmp\n",
    "        elif start > end and (tmp := front_1_sum[-2] - front_1_sum[start-1] + front_1_sum[end]) > max_1_num:\n",
    "          max_1_num = tmp\n",
    "        else:\n",
    "          tmp = -1\n",
    "\n",
    "        print(start, end, tmp)\n",
    "\n",
    "        start += 1\n",
    "        if end + 1 >= len(nums):\n",
    "          end = 0\n",
    "        else:\n",
    "          end += 1\n",
    "\n",
    "      return count_1 - max_1_num\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        t, ans = 0, len(nums)\n",
    "        pre = [0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                pre[i] = 1-nums[i]\n",
    "            else:\n",
    "                pre[i] = pre[i-1]+1-nums[i]\n",
    "            if nums[i]:\n",
    "                t += 1\n",
    "        bak = [0]*len(nums)\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            if i == len(nums)-1:\n",
    "                bak[i] = 1-nums[i]\n",
    "            else:\n",
    "                bak[i] = bak[i+1]+1-nums[i]\n",
    "        for i in range(len(nums)):\n",
    "            j = i+1-t\n",
    "            if j < 0:\n",
    "                cur = pre[i]+bak[j]\n",
    "            else:\n",
    "                if j == 0:\n",
    "                    cur = pre[i]\n",
    "                else:\n",
    "                    cur = pre[i]-pre[i-t]\n",
    "            ans = min(ans, cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # nums = nums+nums\n",
    "        s = [nums[0]]\n",
    "        for i in range(1,n):\n",
    "            s.append( nums[i]+s[i-1])\n",
    "        m = s[n-1]\n",
    "        for i in range(n,2*n):\n",
    "            s.append(m+s[i-n])\n",
    "        # print(s)\n",
    "        ans = n\n",
    "        for i in range(n,2*n):\n",
    "                tmp = s[i]-s[i-m]\n",
    "                ans = min(ans,m-tmp)\n",
    "                # print(i,j,tmp, ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        nums += nums\n",
    "        n = len(nums)\n",
    "        pres = [0]\n",
    "        for i in range(n):\n",
    "            pres.append(pres[-1] + (1 if nums[i] == 1 else 0))\n",
    "\n",
    "        # 数组中1的总个数为\n",
    "        cnt = pres[n // 2]\n",
    "        ans = cnt\n",
    "\n",
    "        # 计算滑窗中最多的1的个数\n",
    "        for i in range(cnt, n):\n",
    "            ans = min(ans, cnt - (pres[i] - pres[i-cnt]))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        one = 0\n",
    "        for x in nums:\n",
    "            if x == 1:\n",
    "                one += 1\n",
    "        nums += nums\n",
    "        n = len(nums)\n",
    "        presum = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                presum[i] = nums[i]\n",
    "            else:\n",
    "                presum[i] = presum[i-1] + nums[i]\n",
    "        # print(presum)\n",
    "        res = 1e9+7\n",
    "        for i in range(n):\n",
    "            if i+1 < one:\n",
    "                continue\n",
    "            if i+1-one==0:\n",
    "                res = min(res, one-presum[i])\n",
    "            else:\n",
    "                # print(presum[i]-presum[i+1-one-1])\n",
    "                res = min(res, one-(presum[i]-presum[i+1-one-1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_presum(self, nums):\n",
    "        pre_sum = []\n",
    "        sum_tmp = 0\n",
    "        for num in nums:\n",
    "            sum_tmp += num\n",
    "            pre_sum.append(sum_tmp)\n",
    "        return pre_sum\n",
    "        \n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        cnt_sum = sum(nums)\n",
    "        nums.extend(nums)\n",
    "        pre_sum = self.get_presum(nums)\n",
    "        length = len(nums)\n",
    "        min_swap = length/2 - cnt_sum\n",
    "        for i in range(length-cnt_sum):\n",
    "            sum_tmp = pre_sum[i+cnt_sum] - pre_sum[i]\n",
    "            swap_tmp = cnt_sum - sum_tmp\n",
    "            min_swap = min(swap_tmp, min_swap)\n",
    "        return min_swap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        m=sum(i for i in nums)\n",
    "        if m==0:\n",
    "            return 0\n",
    "        nums+=nums\n",
    "        a=list(accumulate(nums))\n",
    "        return m-max(a[i+m-1]-(a[i-1] if i>=1 else 0) for i in range(2*n-m+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        n1 = 0\n",
    "        for i in nums:\n",
    "            if i == 1: n1 += 1\n",
    "        nums = nums + nums[:n1]\n",
    "        ad = [0 for i in range(len(nums))]\n",
    "        for i in range(1, len(nums)): ad[i] = ad[i - 1] + nums[i]\n",
    "        ans = 0\n",
    "        for i in range(0, n):\n",
    "            ans = max(ad[i + n1] - ad[i], ans)\n",
    "        ans = n1 - ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        cnt=0\n",
    "        for i in nums:\n",
    "            if(i==1):\n",
    "                cnt+=1\n",
    "        nums+=nums\n",
    "        n=len(nums)\n",
    "        sum=n*[0]\n",
    "        for i in range(0,n):\n",
    "            if nums[i]==1:\n",
    "                sum[i]+=1\n",
    "            if(i>0):\n",
    "                sum[i]+=sum[i-1]\n",
    "        # for i in sum:\n",
    "            # print(i,end='')\n",
    "        res=int(0)\n",
    "        # res=(int)0\n",
    "        for i in range(cnt-1,n):\n",
    "            x=sum[i]\n",
    "            if(i-cnt>=0):\n",
    "                x-=sum[i-cnt]\n",
    "            res=max(res,x)\n",
    "        print(res)\n",
    "        print(cnt)\n",
    "        # print(res+cnt)    \n",
    "        return cnt-res\n",
    "# a=Solution()\n",
    "# print(a.minSwaps([0,0,1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums+=nums\n",
    "        arr = [0]*(2*n)\n",
    "        for i in range(2*n):\n",
    "            if i>0:\n",
    "                arr[i] = arr[i-1]\n",
    "            if nums[i]==1:\n",
    "                arr[i]+=1\n",
    "        \n",
    "        m = arr[n-1]\n",
    "        \n",
    "        count = arr[m-1]\n",
    "        for i in range(0,n):\n",
    "            count = max(count,arr[i+m]-arr[i])\n",
    "        \n",
    "        return m-count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        cnt = sum(nums)\n",
    "        nums = [0]+nums+nums\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "        ans = float('inf')\n",
    "        for i in range(len(nums)//2):\n",
    "            ans = min(ans,cnt-nums[i+cnt]+nums[i])\n",
    "        return ans\n",
    "    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        t = sum(nums)\n",
    "        lens = len(nums)\n",
    "        nums = nums+nums\n",
    "        arr = []\n",
    "        presum = 0\n",
    "        for n in nums:\n",
    "            arr.append(presum)\n",
    "            if n ==0:\n",
    "                presum+=1\n",
    "        res = t\n",
    "        for i in range(lens):\n",
    "            res = min(arr[i+t]-arr[i],res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        num=len([x for x in nums if x==1])\n",
    "        if num==0:\n",
    "            return 0\n",
    "        ans=1000000\n",
    "        nums=nums+nums[:]\n",
    "        data=[]\n",
    "        for i,x in enumerate(nums):\n",
    "            if x==1:\n",
    "                data.append(i)\n",
    "        for i in range(num):\n",
    "            ans=min(ans,num-(bisect_left(data,data[i]+num)-i))\n",
    "            #print(num-(bisect_left(data,data[i]+num)-i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = sum(nums)\n",
    "        l = len(nums)\n",
    "        nums.extend(nums)\n",
    "        pre = [0 for _ in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                pre[i] = nums[i]\n",
    "            else:\n",
    "                pre[i] = pre[i-1] + nums[i] \n",
    "        print(nums)\n",
    "        ans = n\n",
    "        for i in range(l):\n",
    "            ans = min(n -(pre[i+n]-pre[i]), ans)\n",
    "        return ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = nums+nums\n",
    "        s = [nums[0]]\n",
    "        for i in range(1,n):\n",
    "            s.append( nums[i]+s[i-1])\n",
    "        m = s[n-1]\n",
    "        for i in range(n,2*n):\n",
    "            s.append(m+s[i-n])\n",
    "        # print(s)\n",
    "        ans = n\n",
    "        for i in range(n,2*n):\n",
    "            for j in range(i-m,i-m+1):\n",
    "                tmp = s[i]-s[j]\n",
    "                ans = min(ans,i-j-tmp)\n",
    "                # print(i,j,tmp, ans)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, a: List[int]) -> int:\n",
    "        def fun(a, k):\n",
    "            p = [0 for _ in range(len(a) + 1)]\n",
    "            for i in range(len(a)):\n",
    "                p[i + 1] = p[i] + a[i]\n",
    "            res = 0\n",
    "            for i in range(len(a) - k + 1):\n",
    "                res = max(res, p[i + k] - p[i])\n",
    "            return k - res\n",
    "        return fun(a + a, sum(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        ones, pre = nums.count(1), [0] + list(accumulate(nums * 2))\n",
    "        return min(ones - pre[i] + pre[i - ones] for i in range(ones, len(pre)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        s=[0 for _ in range(2*n+2)]\n",
    "        for i in range(n):\n",
    "            nums.append(nums[i])\n",
    "        for i in range(2*n):\n",
    "            s[i+1]=s[i]+nums[i]\n",
    "        m=s[n]\n",
    "        cnt=0\n",
    "        for i in range(n):\n",
    "            cnt=max(cnt,s[i+m]-s[i])\n",
    "        return m-cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n, m = len(nums), nums.count(1)\n",
    "        sums = [0] + list(accumulate(nums * 2))\n",
    "        return m - max(sums[i + m] - sums[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        ones, pre = nums.count(1), [0] + list(accumulate(nums * 2))\n",
    "        return min(ones - pre[i] + pre[i - ones] for i in range(ones, len(pre)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, a: List[int]) -> int:\n",
    "        tot=sum(a)\n",
    "        if tot<=1: return 0\n",
    "        a=a+a\n",
    "        ss=[0 for i in range(len(a)+1)]\n",
    "        ss[0]=a[0]\n",
    "        l=len(ss)\n",
    "        for i in range(1, l):\n",
    "            ss[i]=ss[i-1]+a[i-1]\n",
    "        x,y=0,1\n",
    "        ans=10**10\n",
    "        for i in range(tot, l):\n",
    "            ans=min(ans, tot-ss[i]+ss[i-tot])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "\n",
    "        c, arr = Counter(nums), nums + nums\n",
    "        n, cnt = len(arr), c[1]\n",
    "        preSum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            preSum[i] = preSum[i - 1] + arr[i - 1]\n",
    "        \n",
    "        l, r, ans = 0, -1, float(\"inf\")\n",
    "        while r < n:\n",
    "            while r + 1 < n and r - l + 1 < cnt:\n",
    "                r += 1\n",
    "            zeroCnt = cnt - (preSum[r + 1] - preSum[l])\n",
    "            ans = min(ans, zeroCnt)\n",
    "            l += 1\n",
    "            r += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = sum(nums)\n",
    "        S = [0] * (2 * n + 1)\n",
    "        nums2 = nums[:] + nums[:]\n",
    "        for i in range(2 * n):\n",
    "            S[i + 1] = S[i] + nums2[i]\n",
    "        maxx = 0\n",
    "        for i in range(2*n - m + 1):\n",
    "            maxx = max(maxx, S[i + m] - S[i])\n",
    "        return m - maxx\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        提示一：1总数是固定的\n",
    "        提示二：1数目固定了最后子数组长度\n",
    "        提示三：题目转换成求循环数组，在长度为k的情况下的最大子数组和\n",
    "        \"\"\"\n",
    "        k=sum(nums)\n",
    "        n=len(nums)\n",
    "        nums_new=nums[:]+nums[:]\n",
    "        presum=list(itertools.accumulate(nums_new,initial=0))\n",
    "        \n",
    "        ans=0\n",
    "        for i in range(2*n-k):\n",
    "            ans=max(ans,presum[i+k]-presum[i])\n",
    "        return k-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        \n",
    "        m = sum(nums)      #原数组1的个数：滑动窗口的长度\n",
    "        nums = nums + nums #头尾相连 ：拼接\n",
    "        n = len(nums)\n",
    "        ans = m\n",
    "        prefixsum = [0] + list(accumulate(nums)) #增加头结点，避免第一个窗口的特殊讨论\n",
    "        for i in range(n - m + 1):\n",
    "            k = m - (prefixsum[m + i] - prefixsum[i])\n",
    "            ans = min(ans, k)\n",
    "        return ans\n",
    "        # for i in range(n-m+1): #利用前缀和统计 m - 滑动1的数目\n",
    "        #     if not i:\n",
    "        #         k = m - prefixsum[m-1]\n",
    "        #     else:\n",
    "        #         k = m - (prefixsum[m + i - 1] - prefixsum[i - 1])\n",
    "        #     ans = min(ans, k)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        ##滑动窗口\n",
    "        ##反向思维，total大小的窗口里最大有几个1？\n",
    "        n=len(nums)\n",
    "        nums+=nums\n",
    "        presum=list(accumulate(nums))\n",
    "        total=presum[n-1]\n",
    "        ans=0\n",
    "        for r in range(total,n+total):\n",
    "            t=presum[r]-presum[r-total]\n",
    "            ans=max(ans,t)\n",
    "        return total-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        presums=[0]\n",
    "        for i in nums: presums.append(presums[-1]+i)     \n",
    "        print(presums)\n",
    "        k=sum(nums) \n",
    "        for i in range(k): \n",
    "            presums.append(presums[-1]+nums[i]) \n",
    "        print(presums)\n",
    "        n=len(nums)\n",
    "        ret=len(nums) \n",
    "        for i in range(1,n+1): \n",
    "            print(i-1,presums[i+k]-presums[i-1])\n",
    "            ret=min(ret,k-(presums[i+k-1]-presums[i-1])) \n",
    "        return ret \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSwaps(self, nums: List[int]) -> int:\n",
    "        ones_count = nums.count(1)\n",
    "    \n",
    "        if ones_count <= 1:\n",
    "            return 0\n",
    "        \n",
    "        n = len(nums)\n",
    "        \n",
    "        # 将输入数组复制一次，构成一个两倍长度的数组\n",
    "        extended_nums = nums + nums\n",
    "        \n",
    "        prefix_sum = [0] * (2 * n)\n",
    "        for i in range(1, 2 * n):\n",
    "            prefix_sum[i] = prefix_sum[i - 1] + extended_nums[i - 1]\n",
    "        \n",
    "        min_swaps = ones_count\n",
    "        for i in range(n, 2 * n):\n",
    "            window_sum = prefix_sum[i] - prefix_sum[i - ones_count]\n",
    "            min_swaps = min(min_swaps, ones_count - window_sum)\n",
    "        \n",
    "        return min_swaps"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
